package 求出MK平均值;

import java.util.*;

/**
 * @Program:IntelliJ IDEA
 * @description: 队列+TreeMap
 * @author:香蕉你个啵娜娜 l.h-p@qq.com
 * @create:2023-01-18 21:32
 **/

public class Solution {
    int k;
    int m;
    int sum = 0;
    Deque<Integer> q = new ArrayDeque<>();
    TreeMap<Integer, Integer> map = new TreeMap<>();
    public MKAverage(int m, int k){
        this.k = k;
        this.m = m;
    }

    public void addElement(int num){
        sum += num;
        if (q.size() == m){
            int n = q.pollFirst();
            sum -= n;
            int left = map.get(n);
            if (left == 1) {
                map.remove(n);
            }else {
                map.put(n, left - 1);
            }
        }
        q.offerLast(num);
        map.put(num, map.getOrDefault(num, 0) + 1);
    }

    public int calculateMKAverage() {
        if (q.size() < m){
            return -1;
        }
        int sum1 = 0;
        int left = k;
        Map<Integer, Integer> rem = new HashMap<>();
        while (left > 0){
            int f = map.firstKey();
            int max = Math.min(left, map.get(f));
            if (max == map.get(f)){
                map.remove(f);
            }else {
                map.put(f, map.get(f) - max);
            }
            rem.put(f, rem.getOrDefault(f, 0) + max);
            left -= max;
            sum1 += f * max;
        }
        left = k;
        while (left > 0){
            int l = map.lastKey();
            int max = Math.min(left, map.get(l));
            if (max == map.get(l)){
                map.remove(l);
            } else {
                map.put(l, map.get(l) - max);
            }
            left -= max;
            sum1 += l * max;
            rem.put(l, rem.getOrDefault(l, 0) + max);
        }
        for (int k : rem.keySet()){
            map.put(k, map.getOrDefault(k, 0) + rem.get(k));
        }
        return (sum - sum1) / (m - 2 * k);
    }


}
